package com.lw.leetcode.str.a;

/**
 * str
 * 459. 重复的子字符串
 *
 * @Author liw
 * @Date 2021/6/28 10:25
 * @Version 1.0
 */
public class RepeatedSubstringPattern {



    public static void main(String[] args) {
        RepeatedSubstringPattern test = new RepeatedSubstringPattern();

        // abcabcabcabc true
        String str = "abcabcabcabc";

        // aba false
//        String str = "aba";

        // abab true
//        String str = "abab";

        // acabc false
//        String str = "acabc";

        // acabcacabc true
//        String str = "acabcacabc";

        boolean b = test.repeatedSubstringPattern(str);
        System.out.println(b);
    }


    public boolean repeatedSubstringPattern(String s) {
        int length = s.length();
        char[] arr = s.toCharArray();

        char end =arr[length - 1];
        int n = find(0,arr,  end);

        int index = 0;
        for (int i = n; i < length; i++) {
            if (arr[i] != arr[index++]) {
                n = find(i - index + 1, arr, end);
                i = n - 1;
                index = 0;
            }
            if (index == n) {
                index = 0;
            }
        }

        return n != length;

    }

    private int find(int start, char[] arr, char end) {
        int length = arr.length;
        int n = 1;
        for (int i = start; i < length; i++) {
            if (arr[i] == end && length % (i + 1) == 0) {
                n = i + 1;
                break;
            }
        }
        return n;
    }

}
